//最短路径
//这里一般考虑的是从一个点到其他所有顶点的路径
//这里需要构建的是有向带权图的api，需要的是有向带权边
//和上面略有不同，不过大差不差
//最短路径一定存在一个最短路径树，我们要做的就是找到这个树
//这个树主要用两个东西表示，一个是edgeTo，表示源点到每个点的路径，一个是distanceTo，表示源点到那一点的距离
//relax:考虑一条新边的时候，是否会给出到这个点的更短的路径，如果是的话，那就更新edgeTo和distanceTo这个点
//最开始原点到原点距离为0，到其他点的距离为正无穷，然后重复relax edge，直到最优情况成立
//下面就是迪杰斯特拉算法了：
//从源点开始，将点所有指向的边都加入优先队列中
//加入之后，开始循环，每次循环如下：
//将最小的distanceTo的点加入最短路径树中，并且加入并relax所有由他发出的边
//直到最后

/**
 *  The {@code DijkstraSP} class represents a data type for solving the
 *  single-source shortest paths problem in edge-weighted digraphs
 *  where the edge weights are non-negative.
 *  <p>
 *  This implementation uses <em>Dijkstra's algorithm</em> with a
 *  <em>binary heap</em>. The constructor takes
 *  &Theta;(<em>E</em> log <em>V</em>) time in the worst case,
 *  where <em>V</em> is the number of vertices and <em>E</em> is
 *  the number of edges. Each instance method takes &Theta;(1) time.
 *  It uses &Theta;(<em>V</em>) extra space (not including the
 *  edge-weighted digraph).
 *  <p>
 *  This correctly computes shortest paths if all arithmetic performed is
 *  without floating-point rounding error or arithmetic overflow.
 *  This is the case if all edge weights are integers and if none of the
 *  intermediate results exceeds 2<sup>52</sup>. Since all intermediate
 *  results are sums of edge weights, they are bounded by <em>V C</em>,
 *  where <em>V</em> is the number of vertices and <em>C</em> is the maximum
 *  weight of any edge.
 *  <p>
 *  For additional documentation,
 *  see <a href="https://algs4.cs.princeton.edu/44sp">Section 4.4</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
import edu.princeton.cs.algs4.DirectedEdge;

public class DijkstraSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private IndexMinPQ<Double> pq;

    public void relax(DirectedEdge e)
    {
        int v=e.from();int w=e.to();
        if(distTo[w]>distTo[v]+e.weight())
        {
            edgeTo[w]=e;
            distTo[w]=distTo[v]+e.weight();
            if(pq.contains(w))  pq.decreaseKey(w,distTo[w]);
            else pq.insert(w, distTo[w]);
        }
    }

    public DijkstraSP(EdgeWeightedDigraph G,int s)
    {
      edgeTo=new DirectedEdge[G.V()];
      distTo=new double[G.V()];
      pq=new IndexMinPQ<Double>(G.V());
     
      for(double i:distTo)
      {
        i=Double.POSITIVE_INFINITY;
      }
      pq.insert(s, 0.0);

      while (!pq.isEmpty()) {
        int v=pq.delMin();
        for(DirectedEdge e:G.adj(v))
        {
            relax(e);
        }
      }
    }

    public double distTo(int v)
    {
      return distTo[v];
    }

    // public Iterable<DirectedEdge> pathTo(int v)
    // {
       
    // }
}
